package com.cheng.algorithm.sort;

import java.util.Arrays;

/**
 * @User Administrator
 * @Classname ShellSort
 * @Project Data-structure-and-algorithm
 * @Description 希尔排序代码实现：交换法
 * 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序;随着增量逐渐减少，每组包含的关键询越来越多，
 * 当增量减至1时，整个文件恰被分成一组，算法便终止
 * @Author wpcheng
 * @Create 2021-08-06-8:56
 * @Version 1.0
 */
public class ExchangeShellSort {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);
    }

    public static void shellSort(int[] arr){
        int temp = 0;
        //根据下面的逐步分析，使用循环处理
        for (int gap = arr.length / 2; gap > 0 ; gap /=2) {
            for (int i = gap; i < arr.length ; i++) {
                for (int j = i-gap; j >=0 ; j-=gap) {
                    if (arr[j] > arr[j+gap]){
                        temp = arr[j+gap];
                        arr[j+gap] = arr[j];
                        arr[j] =  temp;
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }


        //第一轮排序
//        for (int i = 5; i < arr.length ; i++) {
//            for (int j = i-5; j >=0 ; j-=5) {
//                if (arr[j] > arr[j+5]){
//                    temp = arr[j+5];
//                    arr[j+5] = arr[j];
//                    arr[j] =  temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));

//        //第二轮排序
//        for (int i = 2; i < arr.length ; i++) {
//            for (int j = i-2; j >=0 ; j-=2) {
//                if (arr[j] > arr[j+2]){
//                    temp = arr[j+2];
//                    arr[j+2] = arr[j];
//                    arr[j] =  temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
//
//        //第三轮排序
//        for (int i = 1; i < arr.length ; i++) {
//            for (int j = i-1; j >=0 ; j--) {
//                if (arr[j] > arr[j+1]){
//                    temp = arr[j+1];
//                    arr[j+1] = arr[j];
//                    arr[j] =  temp;
//                }
//            }
//        }
//        System.out.println(Arrays.toString(arr));
    }

}
